package com.yangzhe.algorithm.c037;

import java.util.ArrayList;
import java.util.List;

// 收集累加和等于aim的所有路径
// 测试链接 : https://leetcode.cn/problems/path-sum-ii/
public class Code03_PathSumII_LeetCode {

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static List<Integer> currentPath = new ArrayList<>();

    /**
     * 思路：递归遍历
     * <p>
     * 1. 递归实际上还是单线程串行，currentPath用于缓存当前递归中的路径，每轮递归的最后恢复状态，就可以复用这个变量
     * 2. root.left == null && root.right == null代表是叶子节点，需要判断当前路径累加和是否等于目标
     * 3. 如果等于目标，则需要把currentPath深copy到结果数组中
     * 4. currentSum相当于用递归栈记录了当前路径的累加和，就不用每次重复计算了
     *
     * @param root
     * @param aim
     * @return
     */
    public static List<List<Integer>> pathSum(TreeNode root, int aim) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        collectPath(root, aim, result, 0);
        return result;
    }

    public static void collectPath(TreeNode root, int aim, List<List<Integer>> result, int currentSum) {
        currentSum += root.val;
        // 判断是叶子节点
        if (root.left == null && root.right == null) {
            if (currentSum == aim) {
                currentPath.add(root.val);
                // 需要深copy，否则路径修改后，结果里的路径也会被修改
                List<Integer> pathCopy = new ArrayList<>(currentPath);
                result.add(pathCopy);

                currentPath.remove(currentPath.size() - 1);
            }
        }

        if (root.left != null) {
            currentPath.add(root.val);
            collectPath(root.left, aim, result, currentSum);
            // 每轮最后恢复状态
            currentPath.remove(currentPath.size() - 1);
        }

        if (root.right != null) {
            currentPath.add(root.val);
            collectPath(root.right, aim, result, currentSum);
            // 每轮最后恢复状态
            currentPath.remove(currentPath.size() - 1);
        }
    }


}
